/*
 * Shell sort was invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort 
 * by moving out of order elements more than one position at a time. One implementation can be described 
 * as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using 
 * insertion sort. Although this method is inefficient for large data sets, it is one of the fastest algorithms 
 * for sorting small numbers of elements (sets with less than 1000 or so elements). Another advantage of this 
 * algorithm is that it requires relatively small amounts of memory.
 *
 */

#include <iostream>
using namespace std;

void swap(int &a, int &b){
	int c=a;
	a=b;
	b=c;
}

void print_array(int* a, int n, char* sep=" "){
	for(int i=0;i<n;i++){
		cout<<a[i]<<sep;
	}
	cout <<endl;
}

void shell_sort(int A[], int size){
	int i, j, incrmnt, temp;

	for(incrmnt = 1 ; incrmnt<size;incrmnt=incrmnt*3+1);

	while (incrmnt > 0){
		for (i=incrmnt; i < size; i++){
			j = i;
			temp = A[i];
			while ((j >= incrmnt) && (A[j-incrmnt] > temp)){
				A[j] = A[j - incrmnt];
				j = j - incrmnt;
			}
			A[j] = temp;
		}
		incrmnt /= 2;
	}
}

/* Performs an insertion sort on elements of a[] with the given gap.
 * If gap == 1, performs an ordinary insertion sort.
 * If gap >= length, does nothing.
 */
void shellSortPhase(int a[], int length, int gap) {
	int i;
	for (i = gap; i < length; ++i) {
		int value = a[i];
		int j;
		for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
			a[j + gap] = a[j];
		}
		a[j + gap] = value;
	}
}//end for

void shellSort(int a[], size_t length) {
	/*
	 * gaps[] should approximate a geometric progression.
	 * The following sequence is the best known in terms of
	 * the average number of key comparisons made [1]
	 */
	static const int gaps[] = {
		1, 4, 10, 23, 57, 132, 301, 701
	};
	int sizeIndex;

	for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
			sizeIndex >= 0;
			--sizeIndex)
		shellSortPhase(a, length, gaps[sizeIndex]);
}

int main(){
	int array[]={20,2,3,9,1,50,10,5};
	int n=sizeof(array)/sizeof(int);
	cout<<"before\n";
	print_array(array,n);

	shell_sort(array,n);

	cout<<"after\n";
	print_array(array,n);
}
